package com.zxl.support;

import java.util.ArrayList;
import java.util.List;

/**
 * 有向图类
 *
 * @author zhaoxl
 * @date 2024/07/31
 */
public class DirectedGraph {
    /**
     * 存储所有节点
     */
    List<DirectedGraphNode> nodes;

    public DirectedGraph(int size) {
        nodes = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            nodes.add(new DirectedGraphNode(i));
        }
    }

    /**
     * 向图中添加一条有向边。
     *
     * @param from 源头节点id
     * @param to   目标节点id
     */
    public void addEdge(int from, int to) {
        nodes.get(from).neighbors.add(to);
    }

    /**
     * 通过遍历所有节点并调用 dfs 方法，判断有向图是否存在循环依赖
     *
     * @return Boolean 有向图是否存在循环依赖
     */
    public boolean hasCycle() {
        int size = nodes.size();
        boolean[] visited = new boolean[size];
        boolean[] recStack = new boolean[size];

        for (int i = 0; i < size; i++) {
            if (!visited[i]) {
                if (dfs(i, visited, recStack)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 使用深度优先搜索（DFS）检查从指定节点开始的子图是否存在循环。
     *
     * @param node 当前节点的索引，在搜索过程中正在处理的节点。
     * @param visited 一个布尔数组，用于标记图中每个节点是否已被访问。
     *                如果节点已被访问，则相应的元素为 `true`，否则为 `false`。
     * @param recStack 一个布尔数组，用于跟踪当前递归调用路径中的节点。
     *                  如果节点在当前递归路径中，则相应的元素为 `true`，否则为 `false`。
     *                  这个栈用于检测是否存在环路，即节点是否在当前递归路径中出现。
     * @return 如果在当前递归路径中检测到环路，返回 `true`。
     *         如果当前节点及其所有邻居节点不形成环路，返回 `false`。
     */
    private boolean dfs(int node, boolean[] visited, boolean[] recStack) {
        visited[node] = true;
        recStack[node] = true;

        for (int neighbor : nodes.get(node).neighbors) {
            if (!visited[neighbor]) {
                if (dfs(neighbor, visited, recStack)) {
                    return true;
                }
            } else if (recStack[neighbor]) {
                return true;
            }
        }

        recStack[node] = false;
        return false;
    }
}
